package cn.moefly.algorithm.sort;

import java.util.function.BiFunction;

public class QuickSort implements SortAlgoRithm {


    /**
     * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，
     *      则可分别对这两部分记录继续进行排序，以达到整个序列有序。
     *
     * 6.1 算法描述
     * 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
     * 从数列中挑出一个元素，称为 “基准”（pivot）；
     * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
     * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     *
     * 注意项：
     *  1. 需要使用递归
     *  2. 边界问题是必须要注意的事情
     *  3. 取两端为标准数可以避免跳过边界的问题
     *  4. 如果取第一个数为基准数，则边界也取到第一个数，然后从另一端开始扫描移动指针可以避免标准数一开始就已经有序的问题
     *
     */

    BiFunction<Integer,Integer,Boolean> compare;

    @Override
    public int[] sort(int[] source, int type) {
        compare = type == ASC ? GT : LT;
        compare = type == ASC ? GE : LE;
        var arr = source.clone();
        if (arr.length > 1){
            innerSort(arr,0,arr.length-1);
        }
        return arr;
    }

    private void innerSort(int[] arr, int start, int end){
        if (start >= end){
            return;
        }

        int headPtr = start;
        int tailPtr = end;
        int standerPos = start;
        int standerVal = arr[standerPos];

        while (headPtr < tailPtr){
            //如果已经满足排序排序要求，则尾移动
            while (headPtr < tailPtr && compare.apply(standerVal, arr[tailPtr])){
                --tailPtr;
            }

            //如果已经满足排序排序要求，则头移动
            while (headPtr < tailPtr && compare.apply(arr[headPtr], standerVal)){
                ++headPtr;
            }
            if (headPtr < tailPtr){
                switchNum(arr,headPtr++,tailPtr--);
            }
        }
        switchNum(arr,headPtr,standerPos);
        innerSort(arr,start,headPtr-1);
        innerSort(arr,tailPtr+1,end);
    }


    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];

        while (i<j) {
            //先看右边，依次往左递减

            while (temp<=arr[j]&&i<j) {
                j--;
            }

            //再看左边，依次往右递增

            while (temp>=arr[i]&&i<j) {
                i++;
            }

            //如果满足条件则交换
            if (i<j) {
                int z = arr[i];
                int y = arr[j];
                arr[i] = y;
                arr[j] = z;

            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


}
